#ifndef SPW_STRING_H_
#define SPW_STRING_H_
/*
* 1. 代码有很多重复步骤，重构简化。
* 2. 只写一些具代表性的类函数操作
* 3. stl标准库中，动态内存申请时都是实际字符2倍。但该库中只要在字符串追加时动态内存才扩充2倍
     构造函数，assign，operator=动态内存都是字符串大小+1
*/
#include <string.h>
#include <initializer_list>
#include <type_traits>

#include <exception/spw_stdexcept.h>
#include <iterator/spw_iterator.h>
#include <memory/spw_alloc.h>
#include <spw_config.h>
#include <utility/spw_move_in.h>
#include <algorithm/spw_algo.h>
#include <cassert>

namespace spwstd{
namespace spwstr{
/*C风格字符串转变为字符串类*/
template<typename CharT = char, typename Alloc = DefaultAlloc<CharT> >
class BasicString {
public:
    using AllocT = Alloc;

    using ValueType = CharT;
    using Pointer = CharT*;
    using ConstPointer = const CharT*;
    using Refer = CharT&;
    using ConstRefer = const CharT&;
    using SizeType = typename spwstd::AllocTraits<AllocT>::SizeType;
    using DifferType = typename spwstd::AllocTraits<AllocT>::DifferType;
    using Iter = spwstd::NormalIterator<Pointer, BasicString>;
    using ConstIter = spwstd::NormalIterator<ConstPointer, BasicString>;

private:
    // AllocT 基本为空基类, string 核心数据
    struct DataAlloc: AllocT {
        DataAlloc(Pointer p, SizeType l, AllocT a=AllocT())
            : AllocT{a}, data_ptr_{p}, data_length_{l}{}
        Pointer data_ptr_; // 指向字符串
        SizeType data_length_; // 字符串长度
    } str_info_;

    static constexpr int s_LocalCapacity = 15 / sizeof(ValueType);
    static const SizeType s_Npos = static_cast<SizeType>(-1);

    union {
        ValueType local_buf_[ s_LocalCapacity + 1 ]; // 本地内存, 保存小字符串
        SizeType alloc_capacity_; // 当本地内存不够，使用动态分配内存. 这里保存分配的capacity大小 
    };

protected:
/*一些内部使用函数*/
    // beg,end模式, [beg,end)区间内字符串赋值
    // 可以是普通指针
    template<typename It>
    void CopyFrom_in(It beg, It end);

    // 检查起始字符有没有超过要复制字符串的范围, 超出范围抛出异常out_of_range
    SizeType Check_in(SizeType first, const char* str) const {
        if(first > this->Size())
            throw spwstd::spwexcept::OutOfRange(str); 
        return first;
    }

    void SetLength_in(SizeType n) {
        this->str_info_.data_length_ = n;
        this->str_info_.data_ptr_[n] = ValueType();
    }

    void SetCapacity_in(SizeType n) {
        if (str_info_.data_ptr_ != local_buf_)
            this->alloc_capacity_ = n;
    }

    // 如果num超过字符串范围，返回字符串末尾，没有还为num
    SizeType Limit_in(SizeType first, SizeType num) const noexcept
    {
        const bool testoff = num < this->Size() - first;
        return testoff ? num : this->Size() - first;
    }

    bool IsLocal_in() const noexcept
    { return Data() == &*local_buf_; }

    void Dispose_in() noexcept
    {
        if(!IsLocal_in()) {
            str_info_.deallocate(str_info_.data_ptr_, alloc_capacity_);
        }
    }

    void Mutate_in(const CharT* s, SizeType len);
    // 分配动态内存. 分配容量cap = 2*old_cap, 只要在字符串追加重新分配时才调用
    Pointer Create_in(SizeType& cap, SizeType old_cap);

    // 追加字符
    BasicString& Append_in(const CharT* s, SizeType n)
    {
        const SizeType len =  n + Size();
        //SizeType want_cap = len;
        if(len <= Capacity()) {
            if(n) {
                Copy_in(Data()+Size(), s, n);
            }
        } else {
            Mutate_in(s, n);
        }
        SetLength_in(len);
        return *this;
    }

    static void Copy_in(CharT* d, const CharT* s, SizeType n)
    {
        for(SizeType i=0; i<n; ++i) {
            d[i] = s[i];
        }
    }

    void Erase_in(SizeType pos, SizeType n);
    BasicString& Replace_in(SizeType pos, SizeType len1, const CharT* s, const SizeType len2);

public:
/* 构造函数和operator */
    // 默认构造函数，构造一个空字符串
    BasicString(): str_info_{ local_buf_, 0 }
    { local_buf_[0] = ValueType{}; }

    BasicString(const BasicString& s, const Alloc &a = Alloc())
        : str_info_{ local_buf_, s.Size(), a}
    { CopyFrom_in(s.Data(), s.Data() + s.str_info_.data_length_); }

    // const char* 可以隐式转化为 BasicString<>
    BasicString(const CharT *ch, const Alloc &a = Alloc())
        : str_info_{local_buf_, 0, AllocT(a)}
    { CopyFrom_in(ch, ch + strlen(ch)); }

    template<typename Iter, typename = std::enable_if<
        std::is_convertible_v<
            typename spwstd::IteratorTraits<Iter>::IteratorCategory,
            spwstd::InputIterTag>>>
    BasicString(Iter first, Iter last, const Alloc& a = Alloc())
    : str_info_{local_buf_, 0, a}
    {
        CopyFrom_in(first, last);
    }

    // 移动构造，主要移动字符串，
    // 如果字符串保存在类的内部，直接赋值
    // 如果字符串在动态内存中保存，则把字符串指针赋给该类，原指针赋值本地buf
    BasicString(BasicString&& str): str_info_{local_buf_, 0, spwuti::move(str.str_info_)} 
    {
        if(str.IsLocal_in()) {
            CopyFrom_in(str.Data(), str.Data()+str.Size());
        } else {
            str_info_.data_ptr_ = str.str_info_.data_ptr_;
            str_info_.data_length_ = str.str_info_.data_length_;
            alloc_capacity_ = str.alloc_capacity_;
            str.alloc_capacity_ = 0;
            str.str_info_.data_ptr_ = str.local_buf_;
            str.str_info_.data_length_ = 0;
        }
    }

    BasicString(std::initializer_list<CharT> l, const Alloc& a=Alloc())
        : str_info_{local_buf_, 0 , a}
    {
        CopyFrom_in(l.begin(), l.end());
    }

    // TODO: 由string_view 构造

    ~BasicString() { Dispose_in(); }

    BasicString& operator=(const BasicString& str) {
        return this->Assign(str);
    } 

    BasicString& operator=(const CharT* s) {
        return this->Assign(s);
    } 

    BasicString& operator=(BasicString&& str) {
        this->Assign(spwuti::move(str));
        return *this;
    }

    BasicString& operator=(std::initializer_list<CharT> l) {
        this->Assign(l);
        return *this;
    }

    BasicString& operator+=(const BasicString& str) {
        return Append(str);
    }

    BasicString& operator+=(const CharT* str) {
        return Append(str);
    }

    AllocT GetAlloc() const noexcept { return str_info_; }

public:
/* 基础函数 */
    /* 元素访问 */
    ConstRefer operator[](SizeType pos) const 
    {
        // 边界检测, 超出边界抛出异常
        if(pos > Size() || Size() == 0) {
            throw spwexcept::OutOfRange("BasicString::operator[]");
        }
        return Data()[pos];
    }

    Refer operator[](SizeType pos) 
    {
        if(pos > Size() || Size() == 0) {
            throw spwexcept::OutOfRange("BasicString::operator[]");
        }
        return Data()[pos];
    }

    // 和operator[]一样. 但在stl标准中at进行边界检测，operator[]不进行边界检测
    ConstRefer At(SizeType n) const
    { return operator[](n); }

    Refer At(SizeType n)
    { return operator[](n); }

    ConstRefer Front() const noexcept
    { return operator[](0); }

    Refer Front() noexcept
    { return operator[](0); }

    ConstRefer Back() const noexcept
    { return operator[](Size()-1); }

    Refer Back() noexcept
    { return operator[](Size() -1); }

    const CharT* Data() const noexcept { return str_info_.data_ptr_; }
    CharT* Data() noexcept { return str_info_.data_ptr_; }
    const CharT* C_str() const noexcept { return str_info_.data_ptr_; }

    /* 迭代器 */
    Iter Begin() noexcept { return Iter(str_info_.data_ptr_); }
    ConstIter Begin() const noexcept { return ConstIter(Data()); }
    Iter End() noexcept { return Iter(str_info_.data_ptr_+this->Size());}
    ConstIter End() const noexcept { return ConstIter(Data()+this->Size());}
    ConstIter Cbegin() const noexcept { return ConstIter(Data()); }
    ConstIter Cend() const noexcept { return ConstIter(Data()+this->Size());}

    /* 容量 */
    SizeType Capacity() const noexcept
    {
        return IsLocal_in() ? s_LocalCapacity : alloc_capacity_;
    }

    SizeType Size() const noexcept { return this->str_info_.data_length_; }

    bool Empty() const noexcept { return this->Size() == 0; }
    // 让容量回复到和字符串数量相同大小, 等同于reserver();
    void ShrinkToFit() noexcept 
    {
        if(Capacity() > Size()) // 当两者相等时不执行
        {
            try{ // reserve可能在分配动态内存时抛出异常，
                 // 但该函数为noexcept，在函数内捕获异常，不让其抛出
                Reserve(0);
            } catch(...) { }
        }
    }

    // 给定字符容量
    void Reserve(SizeType res=0);

/* 操作函数 */
    /* 修改 */
    // Assign 操作和构造函数操作，区别就是 执行Assign操作的string原先有数据或动态内存已经分配。
    // 当Assign 赋值的字符串大小没有超过原先分配内存，可以直接使用
    BasicString& Assign(const BasicString& str);
    BasicString& Assign(BasicString&& str);
    BasicString& Assign(const CharT* s);
    BasicString& Assign(std::initializer_list<CharT> l);

    // 只是设置字符长度为0，不会改变容量，也不会释放动态内存
    void Clear() noexcept
    {
        str_info_.data_length_ = 0;
        SetLength_in(0);
    }

    // 重设字符串大小，大于原字符串数量用ch填充
    void Resize(SizeType n, CharT ch=CharT());

    BasicString& Erase(SizeType pos=0, SizeType n=s_Npos);
    Iter Erase(ConstIter pos);
    Iter Erase(ConstIter first, ConstIter last);

    void PushBack(CharT ch);
    void PopBack();

    BasicString& Append(const CharT* s, SizeType n=s_Npos);
    BasicString& Append(const BasicString& str, SizeType pos=0, SizeType n=s_Npos);
    BasicString& Append(SizeType n, CharT c);

    // 插入insert, 特殊化的replace
    BasicString& Insert(SizeType pos, const BasicString& str) {
        return Replace(pos, 0, str.Data());
    }

    BasicString& Insert(SizeType pos, const CharT* s);

    BasicString& Insert(ConstIter pos, const BasicString& str)
    {
        return Replace(pos-Begin(), 0, str.Data());
    }

    BasicString& Insert(ConstIter pos, const CharT* str) 
    {
        return Replace(pos-Begin(), 0, str);
    }

    template<typename Iter, typename = std::enable_if<
        std::is_convertible_v<
            typename spwstd::IteratorTraits<Iter>::IteratorCategory,
            spwstd::InputIterTag>>>
    BasicString& Insert(ConstIter pos, 
                         Iter first2, Iter last2)
    {
        BasicString tmp(first2, last2);
        return Replace(pos-Begin(), 0, tmp);
    }

    BasicString& Insert(ConstIter pos, std::initializer_list<CharT> l) 
    {
        BasicString tmp(l);
        return this->Replace(pos, pos, tmp);
    }

    BasicString& Replace(SizeType pos, SizeType count, const BasicString& str) {
        return Replace(pos, count, str.Data());
    }

    BasicString& Replace(SizeType pos, SizeType count, const CharT* s);

    BasicString& Replace(ConstIter first, ConstIter last, const BasicString& str)
    {
        return Replace(first, last, str.Data());
    }

    BasicString& Replace(ConstIter first, ConstIter last, const CharT* str) 
    {
        return Replace(first-Begin(), last-first, str);
    }

    template<typename Iter, typename = std::enable_if<
        std::is_convertible_v<
            typename spwstd::IteratorTraits<Iter>::IteratorCategory,
            spwstd::InputIterTag>>>
    BasicString& Replace(ConstIter first1, ConstIter last1, 
                         Iter first2, Iter last2)
    {
        BasicString tmp(first2, last2);
        return Replace(first1, last1, tmp);
    }

    BasicString& Replace(ConstIter first, ConstIter last, std::initializer_list<CharT> l) 
    {
        BasicString tmp(l);
        return this->Replace(first, last, tmp);
    }

    // 不检测dest范围
    SizeType Copy(CharT* dest, SizeType n, SizeType pos = 0) const;

    void Swap(BasicString& other) noexcept;

    /* 操作 */
    // 比较，compare
    int Compare(const BasicString& other) const;
    // 返回字串, substr
    BasicString Substr(SizeType pos=0, SizeType n=s_Npos) const
    {
        Check_in(pos, "basicstring::substr");
        n = Limit_in(0, n);
        return BasicString(Data()+pos, Data()+pos+n);
    }

    /* 查找 */
    // TODO: find
};

template<typename CharT,  typename Alloc>
void BasicString<CharT, Alloc>::Mutate_in(const CharT* s, SizeType len)
{
    SizeType new_cap = Size() + len;
    Pointer ptr = Create_in(new_cap, Capacity());
    if (Size()) {
        Copy_in(ptr, Data(), Size());
    }
    if (s&&len) {
        Copy_in(ptr+Size(), s, len);
    }
    Dispose_in();
    str_info_.data_ptr_ = ptr;
    SetCapacity_in(new_cap);
}

template<typename CharT,  typename Alloc>
void BasicString<CharT, Alloc>::Erase_in(SizeType pos, SizeType n)
{
    // erase()调用erase_in()保证了，在字符串范围内发生
    // 因为是移除，原capacity肯定够用
    // Size(), pos-1, n; Size()-pos+1 -n
    Copy_in(Data()+pos, Data()+pos+n, Size() - pos+1 - n);
}

template<typename CharT,  typename Alloc>
BasicString<CharT, Alloc>& 
BasicString<CharT, Alloc>::Replace_in(SizeType pos, SizeType len1, 
                                            const CharT* s, const SizeType len2)
{
    // 检测替换后有没有超过分配器分配能力
    if (pos > Size())
        throw spwexcept::OutOfRange("basicstring::replace_in");

    SizeType max_num = (SizeType(-1) / sizeof(CharT));
    if(max_num - (Size()-len1) < len2)
        throw spwexcept::LengthError("basicstring::replace_in");
    const SizeType old_size = Size();
    const SizeType new_size = old_size + len2 - len1;
    const SizeType how_much = old_size - pos - len1; //原字符串替换右侧剩余字符数
    if(new_size <= Capacity()) {
        CharT* p = Data() + pos;
        // how_much复制到相应位置
        if(len1>len2)
            Copy_in(p+len2, p+len1, how_much);
        else {
            for(SizeType i=0; i<=how_much; ++i) {
                Data()[new_size-i] = Data()[old_size-i];
            }
        }
        // 把len2长的const char*复制到相应位置
        for(SizeType i=0; i<len2; ++i)
        {
            p[i] = s[i];
        }
    }
    else
    {
        SizeType cap = new_size;
        auto ptr = Create_in(cap, Capacity()); 
        Copy_in(ptr, Data(), pos);
        Copy_in(ptr+pos, s, len2);
        Copy_in(ptr+pos+len2, Data()+pos+len1, how_much);
        Dispose_in();
        str_info_.data_ptr_ = ptr;
        SetCapacity_in(cap);
    }
    SetLength_in(new_size);

    return *this;
}

template<typename CharT,  typename Alloc>
typename BasicString<CharT, Alloc>::Pointer
BasicString<CharT, Alloc>::Create_in(SizeType& cap, SizeType old_cap) {
    // 分配最大容量数，stl标准库是有Alloc绝定。本库中分配器没有max_size(). 这里简化
    SizeType max_num = (SizeType(-1) / sizeof(CharT) - 1) / 2;
    if(cap > max_num)
        throw spwexcept::LengthError("BasicString::create_in over lenght");

    if (cap>old_cap && cap<2*old_cap) {
        cap = 2*old_cap;
    }
    return str_info_.allocate(cap+1);
}

template<typename CharT,  typename Alloc>
template<typename It>
void BasicString<CharT, Alloc>::CopyFrom_in(It beg, It end) {
    auto diff = end - beg;
    if(diff <= s_LocalCapacity) {
        // 把s中local_buf_内的字符串复制到该local_buf_
        auto tmp_iter = beg;
        for(int i=0; i<diff; ++i) {
            this->local_buf_[i] = *tmp_iter++;
        }
    } else {
        // 生成Size()+1大小动态内存，把s内字符串复制给该对象
        auto tmp_iter = beg;
        CharT* ptr = str_info_.allocate(diff+1);
        for(int i=0; i<diff; ++i) {
            ptr[i] =  *tmp_iter++;
        }

        str_info_.data_ptr_ = ptr;
        alloc_capacity_ = diff;
    }
    SetLength_in(diff);
}

template<typename CharT, typename Alloc>
void BasicString<CharT, Alloc>::Reserve(SizeType res) {
    if ( res < Size())
        res = Size();
    const SizeType cap = Capacity(); // cap >= s_LocalCapacity
    if (res != cap) {
        if (res > cap || res > s_LocalCapacity) // 使用了动态内存 
        {
            Pointer ptr = Create_in(res, cap);
            for(SizeType i=0; i<Size(); ++i)
            {
                ptr[i] = Data()[i];
            }
            Dispose_in();
            str_info_.data_ptr_ = ptr;
            alloc_capacity_ = res;
        }
        else if(!IsLocal_in()) // res小于s_LocalCapacity并且使用的是动态内存
        {
            for(SizeType i=0; i<Size(); ++i)
            {
                local_buf_[i] = Data()[i];
            }
            Dispose_in();
            str_info_.data_ptr_ = local_buf_;
        }
    }
    SetLength_in(Size());
}

template<typename CharT,  typename Alloc>
BasicString<CharT, Alloc>& 
BasicString<CharT, Alloc>::Assign(const BasicString& str) 
{
    if (this != &str) {
        const SizeType rsize = str.Size();
        const SizeType capac = Capacity();
        // capacity() 一定大于15
        if (rsize > capac) {
            CharT* ptr = str_info_.allocate(rsize + 1);
            // 如果原来有动态内存分配的字符串，释放
            Dispose_in();
            str_info_.data_ptr_ = ptr;
            alloc_capacity_ = rsize;
        }

        if (rsize) {
            for(SizeType i=0; i< rsize; ++i) {
                str_info_.data_ptr_[i] = *(str.Data() + i);
            }
        }

        SetLength_in(rsize);
    }
    return *this;
}

template<typename CharT,  typename Alloc>
BasicString<CharT, Alloc>& 
BasicString<CharT, Alloc>::Assign(BasicString&& str) 
{
    // 如果str是本地，复制；如果str存在动态内存，只复制指针
    if (str.IsLocal_in())
    {
        for(SizeType i=0; i<str.Size(); ++i) 
        {
            local_buf_[i] = str.local_buf_[i];
        }
        str_info_.data_ptr_ = local_buf_;
        SetLength_in(str.Size());
        // 可能本地不保存在local_buf_而保存在动态内存中
        str.SetLength_in(0);
    } else {
        str_info_.data_ptr_ = str.str_info_.data_ptr_;
        alloc_capacity_ = str.alloc_capacity_;
        SetLength_in(str.str_info_.data_length_);

        str.alloc_capacity_ = 0;
        str.str_info_.data_ptr_ = str.local_buf_;
        str.SetLength_in(0);
    }
    return *this;
}

template<typename CharT,  typename Alloc>
BasicString<CharT, Alloc>& 
BasicString<CharT, Alloc>::Assign(const CharT* s)
{
    auto n = strlen(s);
    const SizeType capac = Capacity();
    if (n > capac) {
        CharT* ptr = str_info_.allocate(n+1);
        Dispose_in();
        str_info_.data_ptr_ = ptr;
        alloc_capacity_ = n;
    }

    if(n) {
        for(SizeType i=0; i<n; ++i) {
            str_info_.data_ptr_[i] = s[i];
        }
    }
    SetLength_in(n);

    return *this;
} 

template<typename CharT,  typename Alloc>
BasicString<CharT, Alloc>& 
BasicString<CharT, Alloc>::Assign(std::initializer_list<CharT> l)
{
    SizeType lsize = l.size();
    SizeType capac = Capacity();
    if(lsize > capac) {
        CharT* ptr = str_info_.allocate(lsize+1);
        Dispose_in();
        str_info_.data_ptr_ = ptr;
        alloc_capacity_ = lsize;
    }

    if(lsize) {
        SizeType i = 0;
        for(char ch : l) {
            str_info_.data_ptr_[i++] = ch;
        }
    }
    SetLength_in(lsize);
    return *this;
}

template<typename CharT,  typename Alloc>
BasicString<CharT, Alloc>& 
BasicString<CharT, Alloc>::Append(SizeType n, CharT ch) {
    if(n)
    {
        // 检测添加字符后，容量有没有超过分配器分配最大份额. 这里简化不检测
        const SizeType len = n + Size();
        SizeType want_cap = len;

        if(want_cap > Capacity()) {
            CharT* ptr = Create_in(want_cap, Capacity());
            Copy_in(ptr, Data(), Size());
            for(SizeType i=0; i<n; ++i) {
                ptr[Size()+i] = ch; 
            }
            str_info_.data_ptr_ = ptr;
            SetCapacity_in(want_cap);
        } else {
            for(SizeType i=0; i<n; ++i)
            {
                Data()[Size()] = ch;
            }
        }
        SetLength_in(len);
    }
    return *this;
}

template<typename CharT,  typename Alloc>
BasicString<CharT, Alloc>& 
BasicString<CharT, Alloc>::Append(const CharT* s, SizeType n) {
    SizeType len = strlen(s);
    if(n>len)
        n = len;
    return Append_in(s, n);
}

template<typename CharT,  typename Alloc>
BasicString<CharT, Alloc>& 
BasicString<CharT, Alloc>::Append(const BasicString& str, SizeType pos, SizeType n) 
{
    return Append_in(str.Data() 
           + str.Check_in(pos, "error at append(const basicstring, SizeType pos, SizeType n)"),
            str.Limit_in(pos, n));
}

template<typename CharT,  typename Alloc>
void BasicString<CharT, Alloc>::PushBack(CharT ch) {
    Append(1, ch);
}

template<typename CharT,  typename Alloc>
void BasicString<CharT, Alloc>::PopBack() {
    Erase(Size()-1, 1);
}

template<typename CharT,  typename Alloc>
BasicString<CharT, Alloc>& 
BasicString<CharT, Alloc>::Erase(SizeType pos, SizeType n)
{
    Erase_in(Check_in(pos,"error in erase(SizeType, SizeType)"), Limit_in(pos, n));
    str_info_.data_length_ -= Limit_in(pos,n);
    return *this;
}

template<typename CharT,  typename Alloc>
typename BasicString<CharT, Alloc>::Iter 
BasicString<CharT, Alloc>::Erase(ConstIter pos)
{
    Erase_in(pos-Begin(), 1);
    str_info_.data_length_ -= 1;
    return Iter((Data()+(pos-Begin())));
}

template<typename CharT,  typename Alloc>
typename BasicString<CharT, Alloc>::Iter 
BasicString<CharT, Alloc>::Erase(ConstIter first, ConstIter last)
{
    Erase_in(first-Begin(), last-first);
    str_info_.data_length_ -= last-first;
    return Iter(Data()+(first-Begin()));
}

template<typename CharT,  typename Alloc>
BasicString<CharT, Alloc>& 
BasicString<CharT, Alloc>::Insert(SizeType pos, const CharT* s)
{
    return Replace_in(pos, 0, s, strlen(s));
}

template<typename CharT,  typename Alloc>
BasicString<CharT, Alloc>& 
BasicString<CharT, Alloc>::Replace(SizeType pos, SizeType count, const CharT* s)
{
    if(count > Size()-pos)
        count = Size() - pos;
    return Replace_in(pos, count, s, strlen(s));
}

template<typename CharT,  typename Alloc>
void BasicString<CharT, Alloc>::Resize(SizeType n, CharT ch) {
    if(n > Size()){
        SizeType count = n - Size();
        Append(count, ch);
    } else if(n < Size()) {
        Erase(n);
    }
}

template<typename CharT,  typename Alloc>
typename BasicString<CharT, Alloc>::SizeType 
BasicString<CharT, Alloc>::Copy(CharT* dest, SizeType n, SizeType pos) const
{
    Check_in(pos, "basicstring::copy");
    n = Limit_in(pos, n);
    if (n)
        Copy_in(dest, str_info_.data_ptr_ + pos, n);

    return n;
}

template<typename CharT,  typename Alloc>
void BasicString<CharT, Alloc>::Swap(BasicString& other) noexcept
{
    if (this == &other)
        return;

    // this 与 other的 Alloc相同，并且空类，不需要交换，只交换内部data数据与length
    if (IsLocal_in()) {
        if (other.IsLocal_in()) {
            CharT tmpdata[s_LocalCapacity + 1];
            Copy_in(tmpdata, other.local_buf_, s_LocalCapacity+1);
            Copy_in(other.local_buf_, this->local_buf_, s_LocalCapacity+1);
            Copy_in(this->local_buf_, tmpdata, s_LocalCapacity+1);
        } else {
            const SizeType tmp_capacity = other.Capacity();
            Copy_in(other.local_buf_, this->local_buf_, s_LocalCapacity+1);
            this->str_info_.data_ptr_ = other.str_info_.data_ptr_;
            other.str_info_.data_ptr_ = other.local_buf_;
            SetCapacity_in(tmp_capacity);
        }
    } else {
        const SizeType tmp_capacity = Capacity();
        if (other.IsLocal_in()) {
            Copy_in(this->local_buf_, other.local_buf_, s_LocalCapacity+1);
            other.str_info_.data_ptr_ = this->str_info_.data_ptr_;
            this->str_info_.data_ptr_ = this->local_buf_;
        } else {
            Pointer tmp_ptr = this->str_info_.data_ptr_;
            this->str_info_.data_ptr_ = other.str_info_.data_ptr_;
            other.str_info_.data_ptr_ = tmp_ptr;
            SetCapacity_in(other.alloc_capacity_);
        }
        other.SetCapacity_in(tmp_capacity);
    }

    const SizeType tmp_length = this->Size();
    SetLength_in(other.Size());
    other.SetLength_in(tmp_length);
}

template<typename CharT,  typename Alloc>
int BasicString<CharT, Alloc>::Compare(const BasicString& other) const
{
    const SizeType size = this->Size();
    const SizeType osize = other.Size();
    const SizeType len = spwstd::spwalg::min(size, osize);

    for (SizeType i=0; i<len; ++i) {
        if (Data()[i] < other.Data()[i]) {
            return -1;
        } else if (Data()[i] == other.Data()[i]) {
            continue;
        } else {
            return 1;
        }
    }

    if (Size() > other.Size()) {
        return 1;
    } else if (Size() < other.Size()) {
        return -1;
    } else {
        return 0;
    }

    assert("cant come here");
}

using String = BasicString<>;
} // namespace spwstr
} // namespace spwstd

#endif
